翻訳と辞書
Words near each other
・ Subha Sankalpam
・ Subhadra
・ Subhadra (disambiguation)
・ Subhadra Joshi
・ Subhadra Kumari Chauhan
・ Subhadra Nambudiri Foundation
・ Subhadra Pradhan
・ Subhadram
・ Subhadrangi
・ Subhajit Saha
・ Subhakankshalu
・ Subhalekha
・ Subhalekha Sudhakar
・ Subhalide
・ Subhamastu
Subhamiltonian graph
・ Subhan Ali Khan Kamboh
・ Subhan Allah
・ Subhan Bakhsh
・ Subhan Quli Qutb Shah
・ Subhan Raza Khan
・ Subhanallah (song)
・ Subhang
・ Subhani ba Yunus
・ Subhankar Banerjee
・ Subhankar Das
・ Subhanpur
・ Subhanpura
・ Subhaprasanna
・ Subharaja of Anuradhapura


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Subhamiltonian graph : ウィキペディア英語版
Subhamiltonian graph
In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.〔.〕〔.〕
==Definition==
A graph ''G'' is subhamiltonian if ''G'' is a subgraph of another graph aug(''G'') on the same vertex set, such that aug(''G'') is planar and contains a Hamiltonian cycle. For this to be true, ''G'' itself must be planar, and additionally it must be possible to add edges to ''G'', preserving planarity,
in order to create a cycle in the augmented graph that passes through each vertex exactly once. The graph aug(''G'') is called a Hamiltonian augmentation of ''G''.〔
It would be equivalent to define ''G'' to be subhamiltonian if ''G'' is a subgraph of a Hamiltonian planar graph, without requiring this larger graph to have the same vertex set. That is, for this alternative definition, it should be possible to add both vertices and edges to ''G'' to create a Hamiltonian cycle. However, if a graph can be made Hamiltonian by the addition of vertices and edges it can also be made Hamiltonian by the addition of edges alone, so this extra freedom does not change the definition.〔For instance in a 2003 technical report "(Book embeddings of graphs and a theorem of Whitney )", Paul Kainen defines subhamiltonian graphs to be subgraphs of planar Hamiltonian graphs, without restriction on the vertex set of the augmentation, but writes that "in the definition of subhamiltonian graph, one can require that the extension only involve the inclusion of new edges."〕

In a subhamiltonian graph, a subhamiltonian cycle is a cyclic sequence of vertices such that adding an edge between each consecutive pair of vertices in the sequence preserves the planarity of the graph. A graph is subhamiltonian if and only if it has a subhamiltonian cycle.〔

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Subhamiltonian graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.